#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
    int tmp[50010];
public:
    int reversePairs(vector<int>& nums)
    {
        return mergeSort(nums, 0, nums.size()-1);
    }

    int mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return 0;
        int ret = 0;
        int mid = (left+right)/2;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);

        int cur1 = left, cur2 = mid+1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] > nums[cur2])
            {
                //ret += right-cur2+1;
                ret += mid-cur1+1;
                //tmp[i++] = nums[cur1++];
                tmp[i++] = nums[cur2++];
            }
            else
            {
                //tmp[i++] = nums[cur2++]; 降序
                tmp[i++] = nums[cur1++];
            }
        }
        while(cur1 <= mid)  tmp[i++] = nums[cur1++];
        while(cur2 <= right)    tmp[i++] = nums[cur2++];

        for(int j=left; j<=right; j++)
            nums[j] = tmp[j-left];
        return ret;
    }
};